home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / FDF101.ARJ / FDF.C < prev    next >
C/C++ Source or Header  |  1992-04-29  |  11KB  |  484 lines
  1. /*
  2.  * fdf.c
  3.  *
  4.  * find duplicates.  searches a given path and its sub-directories for
  5.  * duplicate files.  Duplicate files have the same name, size, date and
  6.  * contents.  However, the definition used by this program can be almost any
  7.  * user-specified combination of the above.
  8.  *
  9.  * Roy Bixler (original development and Atari ST version, maintenance)
  10.  * Ayman Barakat (idea)
  11.  * David Oertel (MS-DOS version)
  12.  *
  13.  * Version 1.0: March 11, 1991 (known as 'mfd - Monk find duplicates')
  14.  * Version 1.01: April 12, 1992 (now 'fdf - find duplicate files')
  15.  *
  16.  * This program is free software; you can redistribute it and/or modify
  17.  * it under the terms of the GNU General Public License as published by
  18.  * the Free Software Foundation; either version 1, or (at your option)
  19.  * any later version.
  20.  *
  21.  * This program is distributed in the hope that it will be useful,
  22.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  23.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24.  * GNU General Public License for more details.
  25.  *
  26.  * You should have received a copy of the GNU General Public License
  27.  * along with this program; if not, write to the Free Software
  28.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  29.  */
  30.  
  31.  
  32. #include <dir.h>
  33. #include <dos.h>
  34. #include <stdlib.h>
  35. #include <stdio.h>
  36. #include <string.h>
  37.  
  38. #include "fdfcomm.h"
  39. #include "fdfstat.h"
  40. #include "elib.h"
  41. #include "fdf.h"
  42.  
  43.  
  44. HASH_LIST *H_list[HASH_TAB_SIZE];
  45.  
  46.  
  47.  
  48. /*
  49.  * print_help
  50.  *
  51.  * prints out the help message for the program
  52.  */
  53. void print_help()
  54.  
  55. {
  56.     printf(FDF_USAGE, PROG_NAME, PROG_NAME);
  57. }
  58.  
  59.  
  60.  
  61. /*
  62.  * show_doc
  63.  *
  64.  * show full documentation
  65.  */
  66. void show_doc()
  67.  
  68. {
  69.     printf(FDF_SCHPIEL);
  70. }
  71.  
  72.  
  73.  
  74. /*
  75.  * add_to_hash_table
  76.  *
  77.  * given a file and a hash table index, add the given file to the hash table
  78.  * at the given index.  Addition is done by putting the new entry at the
  79.  * head of a linked list.
  80.  */
  81. void add_to_hash_table(FILE_LIST *f_name, int h_idx)
  82.  
  83. {
  84.     HASH_LIST *new_entry = malloc((size_t) sizeof(HASH_LIST));
  85.  
  86.     if (new_entry != NULL) {
  87.         new_entry->f_name = f_name;
  88.         new_entry->f_name->printed = 0;
  89.         new_entry->next = H_list[h_idx];
  90.         H_list[h_idx] = new_entry;
  91.     }
  92. }
  93.  
  94.  
  95. /*
  96.  * gen_hash
  97.  *
  98.  * given a linked list repesenting a list of files, generate a hash table for
  99.  * it.
  100.  */
  101. void gen_hash(FILE_LIST *flist)
  102.  
  103. {
  104.     for (;flist != NULL; flist = flist->next) {
  105.         if (!flist->added) {
  106.             if (v_flag) {
  107.                 update_total_bytes(flist->dta.ff_fsize);
  108.                 update_num_files();
  109.             }
  110.             if ((Match_criteria) & (NAMES_MATCH))
  111.                 add_to_hash_table(flist, hashpjw(flist->dta.ff_name));
  112.             else if ((Match_criteria) & (SIZES_MATCH))
  113.                 add_to_hash_table(flist, flist->dta.ff_fsize % HASH_TAB_SIZE);
  114.             else if ((Match_criteria) & (TIMES_MATCH))
  115.                 add_to_hash_table(flist,
  116.                                   ((unsigned long) (flist->dta.ff_fdate << 16) +
  117.                                    (unsigned long) (flist->dta.ff_ftime)) %
  118.                                   HASH_TAB_SIZE);
  119.             flist->added = 1;
  120.         }
  121.     }
  122. }
  123.  
  124.  
  125.  
  126. /*
  127.  * find_duplicated_name
  128.  *
  129.  * scans the generated hash table for names which occur twice (or more).
  130.  * Takes a pointer to hash table index to start the search at, modifies this
  131.  * on return to indicate where it stopped looking (either because of end of
  132.  * hash table or because a duplicated name found).  Return pointer to first
  133.  * occurrence of duplicated name found or NULL if none found.
  134.  */
  135. HASH_LIST *find_duplicated_name(int *h_idx, HASH_LIST *last_found)
  136.  
  137. {
  138.     int i;
  139.     HASH_LIST *anchor, *cur;
  140.  
  141.     anchor = last_found;
  142.     for (i = *h_idx; i < HASH_TAB_SIZE; i++)
  143.         if (H_list[i] != NULL) {
  144.             if (anchor == NULL)
  145.                 anchor = H_list[i];
  146.             for (; anchor != NULL; anchor = anchor->next)
  147.                 if (!anchor->f_name->printed)
  148.                     for (cur = anchor->next; cur != NULL; cur = cur->next)
  149.                         if ((!cur->f_name->printed) &&
  150.                             (cmpflist_eq(anchor->f_name, cur->f_name))) {
  151.                             *h_idx = i;
  152.                             return anchor;
  153.                         }
  154.         }
  155.  
  156.     *h_idx = i;
  157.     return NULL;
  158. }
  159.  
  160.  
  161.  
  162. /*
  163.  * gen_id_menu
  164.  *
  165.  * given a starting point in the file list, generate an interactive delete
  166.  * menu.  Return number of items put into the menu.
  167.  */
  168. int gen_id_menu(HASH_LIST *name_duped, FILE_LIST **menu, int max_items)
  169.  
  170. {
  171.     int n_found = 0;
  172.     long n_bytes = 0L;
  173.     HASH_LIST *cur;
  174.  
  175.     for (cur = name_duped->next;
  176.          ((cur != NULL) && (n_found < max_items));
  177.          cur = cur->next)
  178.         if ((!cur->f_name->printed) &&
  179.             (files_match(name_duped->f_name, cur->f_name))) {
  180.             if (n_found == 0) {
  181.                 if (v_flag)
  182.                     n_bytes += name_duped->f_name->dta.ff_fsize;
  183.                 menu[n_found++] = name_duped->f_name;
  184.             }
  185.             if (v_flag)
  186.                 n_bytes += cur->f_name->dta.ff_fsize;
  187.             menu[n_found++] = cur->f_name;
  188.         }
  189.  
  190.     if ((n_found) && (v_flag)) {
  191.         update_num_which_dupd();
  192.         update_num_dups(n_found, n_bytes);
  193.     }
  194.  
  195.     return n_found;
  196. }
  197.  
  198.  
  199.  
  200. /*
  201.  * id_dups
  202.  *
  203.  * given a pointer to a name which has been determined to be duplicated, print
  204.  * all the names and their path's out and ask the user which ones to delete.
  205.  */
  206. void id_dups(HASH_LIST *start)
  207.  
  208. {
  209.     int n_found, i, n_del;
  210.     FILE_LIST *cur, *menu[N_INTERACTIVE];
  211.     char menu_sel[MAX_STR], which_del[N_INTERACTIVE];
  212.  
  213.     if (!(n_found = gen_id_menu(start, menu, N_INTERACTIVE)))
  214.         return;
  215.     while (1) {
  216.         print_id_menu(menu, n_found);
  217.         printf("\nEnter list of files to delete (hit CR for none)\n");
  218.         fgets(menu_sel, MAX_STR-1, stdin);
  219.         zap_trailing_nl(menu_sel, MAX_STR-1, stdin);
  220.         if (!mark_list(menu_sel, which_del, n_found)) {
  221.              for (n_del=0, i=0; i < n_found; i++)
  222.                   if (which_del[i])
  223.                       if (!delete_path_name_file(menu[i]->path,
  224.                                                 menu[i]->dta.ff_name, '\0')) {
  225.                          n_del++;
  226.                          if (v_flag) {
  227.                               update_total_del_bytes(menu[i]->dta.ff_fsize);
  228.                              if (v_flag > 1) {
  229.                                  printf("Deleted ");
  230.                                  print_fpath(menu[i]->path,
  231.                                              menu[i]->dta.ff_name);
  232.                                  printf("\n");
  233.                              }
  234.                          }
  235.                      }
  236.               break;
  237.           }
  238.       } 
  239.  
  240.      if (n_del)
  241.          printf("\n");
  242.   }
  243.  
  244.  
  245. /*
  246.  * print_dups
  247.  *
  248.  * given a pointer to a name which has been determined to be duplicated, print
  249.  * all the names and their path's out.
  250.  */
  251. void print_dups(HASH_LIST *name_duped)    /* now, who's being duped here? */
  252.  
  253. {
  254.     HASH_LIST *cur;
  255.  
  256.     for (cur = name_duped->next; cur != NULL; cur = cur->next)
  257.         if ((!cur->f_name->printed) &&
  258.             (files_match(name_duped->f_name, cur->f_name))) {
  259.             if (!name_duped->f_name->printed) {
  260.                 if (v_flag) {
  261.                     update_num_which_dupd();
  262.                     update_num_dups(1U, name_duped->f_name->dta.ff_fsize);
  263.                 }
  264.                 print_match_header(name_duped->f_name);
  265.                 print_next_match(name_duped->f_name, -1);
  266.             }
  267.             if (v_flag)
  268.                 update_num_dups(1U, cur->f_name->dta.ff_fsize);
  269.             print_next_match(cur->f_name, -1);
  270.         }
  271.  
  272.     if (name_duped->f_name->printed)
  273.         printf("\n");
  274. }
  275.  
  276.  
  277.  
  278. /*
  279.  * find_non_printed
  280.  *
  281.  * given a pointer to a FILE_LIST, return the pointer to the next element which
  282.  * has not been printed yet.
  283.  */
  284. HASH_LIST *find_non_printed(HASH_LIST *file)
  285.  
  286. {
  287.     for (; ((file != NULL) && (file->f_name->printed)); file = file->next);
  288.     return file;
  289. }
  290.  
  291.  
  292.  
  293. /*
  294.  * find_dups
  295.  *
  296.  * given a path, find the duplicate files and dump them to the standard output.
  297.  */
  298. void find_dups()
  299.  
  300. {
  301.     HASH_LIST *last_found, *f_found;
  302.     int i;
  303.  
  304.     gen_hash(F_list);
  305.     i = 0;
  306.     last_found = NULL;
  307.     while ((i < HASH_TAB_SIZE) &&
  308.            ((f_found = find_duplicated_name(&i, last_found)) != NULL)) {
  309.         if (i_flag)
  310.             id_dups(f_found);
  311.         else
  312.             print_dups(f_found);
  313.         last_found = find_non_printed(f_found->next);
  314.     }
  315. }
  316.  
  317.  
  318.  
  319. /*
  320.  * init_hash
  321.  *
  322.  * insure the hash table is empty
  323.  */
  324. void init_hash()
  325.  
  326. {
  327.     int i;
  328.  
  329.     for (i=0; i<HASH_TAB_SIZE; i++)
  330.         H_list[i] = NULL;
  331. }
  332.  
  333.  
  334.  
  335. /*
  336.  * set_sort_hash_criteria
  337.  *
  338.  * must guarantee that no matter what the matching criteria is, that
  339.  * duplicate files will always go to the same hash table location.
  340.  *
  341.  * This is called to make sure that, when comparing two entries in the same
  342.  * hash table bucket (i.e when calling 'cmpflist_eq()'), appropriate criteria
  343.  * are used to determine if the two entries can possibly match.  There is no
  344.  * real sorting with the hash table!
  345.  */
  346. void set_sort_hash_criteria()
  347.  
  348. {
  349.     if ((Match_criteria) & (NAMES_MATCH))
  350.         Sort_criteria = NAME_SORT;
  351.     else if ((Match_criteria) & (SIZES_MATCH))
  352.         Sort_criteria = SIZE_SORT;
  353.     else if ((Match_criteria) & (TIMES_MATCH))
  354.         Sort_criteria = TIME_SORT;
  355. }
  356.  
  357.  
  358.  
  359. /*
  360.  * get_options
  361.  *
  362.  * get the command-line options, check for consistency and set the appropriate
  363.  * variables.
  364.  */
  365. int get_options(int argc, char **argv)
  366.  
  367. {
  368.     extern int getopt(int argc, char **argv, char *opts);
  369.     extern int Optind;
  370.     extern char *optarg;
  371.     int optchar;
  372.     char a_flag = 0, c_flag = 0, d_flag = 0, n_flag = 0, s_flag = 0;
  373.  
  374.     if (argc < 2) {
  375.         print_help();
  376.         exit(-1);
  377.     }
  378.  
  379.     while ((optchar = getopt(argc, argv, GETOPT_LIST)) != EOF) {
  380.         if (isupper(optchar))
  381.             optchar = tolower(optchar);
  382.         switch (optchar) {
  383.         case 'i':
  384.             i_flag = 1;
  385.             break;
  386.         case 'l':
  387.             l_flag = 1;
  388.             break;
  389.         case 'm':
  390.             if ((optarg == NULL) || (strpbrk(optarg, "AaCcDdNnSs") != optarg)) {
  391.                 printf("%s: must specify 'a' or 'c', 'd', 'n' and/or 's' after -m\n", 
  392.                        PROG_NAME);
  393.                 print_help();
  394.                 exit(-1);
  395.             }
  396.             for (;*optarg != '\0'; optarg++) {
  397.                 if (isupper(*optarg))
  398.                     *optarg = tolower(*optarg);
  399.                 switch (*optarg) {
  400.                 case 'a':
  401.                     a_flag = 1;
  402.                     break;
  403.                 case 'c':
  404.                     c_flag = 1;
  405.                     Match_criteria |= CONTENTS_MATCH;
  406.                     break;
  407.                 case 'd':
  408.                     d_flag = 1;
  409.                     Match_criteria |= TIMES_MATCH;
  410.                     break;
  411.                 case 'n':
  412.                     n_flag = 1;
  413.                     Match_criteria |= NAMES_MATCH;
  414.                     break;
  415.                 case 's':
  416.                     s_flag = 1;
  417.                     Match_criteria |= SIZES_MATCH;
  418.                     break;
  419.                 default:
  420.                     printf("%s: invalid match criteria '%c' specified\n", 
  421.                            PROG_NAME, *optarg);
  422.                     print_help();
  423.                     exit(-1);
  424.                 }
  425.             }
  426.             break;
  427.         case 'v':
  428.             v_flag++;
  429.             break;
  430.         case '?':
  431.             show_doc();
  432.             exit(0);
  433.         default:
  434.             print_help();
  435.             exit(-1);
  436.         }
  437.     }
  438.  
  439.     if (argc == Optind) {
  440.         printf("%s: at least one path specification required\n", PROG_NAME);
  441.         print_help();
  442.         exit(-1);
  443.     }
  444.     else if (a_flag)
  445.         if ((c_flag) || (d_flag) || (n_flag) || (s_flag)) {
  446.             printf("%s: -ma option conflicts with -mc, -md, -mn or -ms\n",
  447.                    PROG_NAME);
  448.             print_help();
  449.             exit(-1);
  450.         }
  451.         else
  452.             Match_criteria = ALL_MATCH;
  453.     else if (!Match_criteria)
  454.         Match_criteria = (TIMES_MATCH|SIZES_MATCH|NAMES_MATCH);
  455.     else if (Match_criteria & CONTENTS_MATCH)
  456.         Match_criteria |= SIZES_MATCH;
  457.     set_sort_hash_criteria();
  458.  
  459.     return Optind;
  460. }
  461.  
  462.  
  463.  
  464. int main(int argc, char **argv)
  465.  
  466. {
  467.     int i;
  468.     char form_path[MAXPATH];
  469.  
  470.     init_hash();
  471.     for (i = get_options(argc, argv); i < argc; i++) {
  472.         format_dir(argv[i], '\0', form_path);
  473.         if (v_flag > 1)
  474.             printf("finding duplicates under %s:\n\n", form_path);
  475.         list_files(PROG_NAME, form_path, (char) 0);
  476.     }
  477.  
  478.     find_dups();
  479.     if (v_flag)
  480.         print_stats();
  481.  
  482.     return(0);
  483. }
  484.